'''
@author: Kevin Zhao
@data:Jan 1,2013 
@note:
merge with min-heap

Exercise 6.5-9
'''

from custom_array import CustomArray
from c6 import *
import math

def min_heapify(A,list_id, index):
    smallest = index
    left_child_index = left(index)
    right_child_index = right(index)
    
    if left_child_index < A.get_heap_size() and A[left_child_index] < A[index]:
        if right_child_index >= A.get_heap_size() or A[left_child_index] < A[right_child_index]:
            smallest = left_child_index
    if right_child_index < A.get_heap_size() and A[right_child_index] < A[index]:
        if left_child_index >= A.get_heap_size() or A[right_child_index] < A[left_child_index]:
            smallest = right_child_index
    if smallest != index:
        exchange(index, smallest, A)
        exchange(index, smallest, list_id)
        min_heapify(A,list_id, smallest)

def build_min_heap(A,list_id):
    A.set_heap_size(len(A))
    for i in range(int(math.floor(len(A) / 2)), -1, -1):
        min_heapify(A,list_id, i)
         
         
def merge(lists):
    final_sorted_list=[]
    heap=CustomArray()
    list_id=[]
    #1.1 pick up the first element of each sorted lists 
    for i in range(len(lists)):
        heap.append(lists[i].pop(0))
        list_id.append(i)
    #1.2 form a min-heap with those picked up elements
    build_min_heap(heap,list_id)
    
    while 1:
        #2 put the root element of the min-heap into the final sorted list
        final_sorted_list.append(heap.pop(0))
    
        #3 replace the root element with the next element from the same list
        list = lists[list_id[0]]
        #encounter empty list
        while len(list) ==0:
            lists.pop(list_id[0])
            if len(lists) == 0:
                while heap.get_heap_size() >0:
                    final_sorted_list.append(heap.pop(0))
                return final_sorted_list#all sorted lists are running out of elements,meaning merge has completed
            list = lists[(list_id[0] + 1) % len(lists)]#next non-empty sorted list
        #replace the root element with the next element from the same list
        heap.insert(0,list.pop(0))
    
        #4 run min-heapify over the root
        min_heapify(heap, list_id, 0)
    
        
        
A = [1,3,5,7,9]
B = [2,4,6,8,10]

print merge([A,B])

        